package acwing._1_1AlgorithmBasic;

import java.util.Arrays;

/**
 * @Project : ProgrammingExercises
 * @Package : ACWing.AlgorithmTemplate
 * @File : PrefixSum.java
 * @Author : WangRuoyu
 * @Date 2023/3/10 11:07
 */

public class _1_4PrefixSum_Diff {
    static int prefixSum1dim(int[] q, int l, int r) { // 一维前缀和
        int res = 0;

        // 求前缀和
        int[] s = new int[q.length + 1];

        for (int i = 1; i < s.length; ++i) {
            s[i] = s[i - 1] + q[i - 1];
        }

        System.out.println(Arrays.toString(s));

        return s[r] - s[l - 1];
    }

    static int prefixSum2dim(int[][] q, int x1, int y1, int x2, int y2) { // 二维前缀和
        int res = 0;

        // 求前缀和
        int[][] s = new int[q.length + 1][q.length + 1];

        for (int i = 1; i < s.length; ++i) {
            for (int j = 1; j < s.length; ++j) {
                s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + q[i - 1][j - 1];
            }
        }

        return s[x2][y2] + s[x1 - 1][y1 - 1] - s[x1 - 1][y2] - s[x2][y1 - 1];
    }

    static void diffInsert1dim(int b[], int l, int r, int c) {
        b[l] += c;
        b[r + 1] -= c;
    }

    static int[] diff1dim(int[] a) { // 一维差分
        int[] b = new int[a.length + 1];

        for (int i = 0; i < b.length - 1; ++i) {
            diffInsert1dim(b, i, i, a[i]);
        }

        return b;
    }

    static void diffInsert2dim(int[][] b, int x1, int y1, int x2, int y2, int c) {
        b[x1][y1] += c;
        b[x2 + 1][y2 + 1] += c;
        b[x2 + 1][y1] -= c;
        b[x1][y2 + 1] -= c;
    }

    static int[][] diff2dim(int[][] a) {// 二维差分
        int[][] b = new int[a.length + 1][a.length + 1];

        for (int i = 0; i < b.length - 1; i++) {
            for (int j = 0; j < b.length - 1; ++j) {
                diffInsert2dim(b, i, j, i, j, a[i][j]);
            }
        }

        return b;
    }
}


